package main

import (
	// "algorithm/sort_Algorithm/select_sort/bubblesort"
	// insertsort "algorithm/sort_Algorithm/insertSort"
	countsort "algorithm/sort_Algorithm/06_counting_sort"
	"fmt"
	"sort"
)

func main() {
	array := []int{3, 5, 8, 1, 6, 0, 7, 2, 4, 9}
	res := countsort.CountSort(array)
	fmt.Println(res)
}

type MyArray struct {
	array []int
}

// 选择排序
// 时间复杂度 O(n^2)，是不稳定排序 空间复杂度O(1)
func (ma *MyArray) selectSort() {
	// 选择伟排序中最小的数
	for j := 0; j < len(ma.array)-1; j++ {
		min := j
		for i := j + 1; i < len(ma.array); i++ {
			if ma.array[min] > ma.array[i] {
				min = i
			}
		}
		// 把最小的数与未排序的第一个数交换位置
		ma.array[min], ma.array[j] = ma.array[j], ma.array[min]
	}

}

func maxProduct(words []string) int {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) > len(words[j])
	})
	n := len(words)
	nums := make([]int, n)
	cnts := make([]int, n)
	for i, word := range words {
		var num int
		for _, c := range word {
			num |= 1 << int(c-'a')
		}
		nums[i] = num
		cnts[i] = len(word)
	}
	var res int
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if cnts[i]*cnts[j] < res {
				break
			}
			if nums[i]&nums[j] == 0 {
				res = cnts[i] * cnts[j]
			}
		}
	}
	return res
}

